package com.li.algorithm.leetcode.hot100;

import java.util.Arrays;

public class Test20 {

    /**
     * 解法1：旋转交换
     *  时间复杂度：O(N^2)
     *  空间复杂度：O(1)
     */
//    public void rotate(int[][] matrix) {
//        //第一行：0 ~ n-1
//        //第二行：1 ~ n-2
//        //第三行：2 ~ n-3
//        int n = matrix.length - 1;
//        //行
//        for (int i = 0; i <= n/2; i++) {
//            int edge = n - i;
//            //列
//            for (int j = i; j <= edge - 1; j++) {
//                int temp = matrix[i][j];
//                matrix[i][j] = matrix[n-j][i];
//                matrix[n-j][i] = matrix[n-i][n-j];
//                matrix[n-i][n-j] = matrix[j][n-i];
//                matrix[j][n-i] = temp;
//            }
//        }
//        for (int i = 0; i < matrix.length; i++) {
//            for (int j = 0; j < matrix.length; j++) {
//                System.out.print(matrix[i][j] + " ");
//            }
//            System.out.println();
//        }
//    }

    /**
     * 解法2：先水平翻转，再沿对角线翻转
     * 水平翻转：matrix[row][col] = matrix[n−row−1][col]
     * 对角线翻转：matrix[row][col] = matrix[col][row]
     *   时间复杂度：O(N^2)
     *   空间复杂度：O(1)
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        //水平翻转：上下颠倒,只需要遍历一半
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - i][j];
                matrix[n - 1 - i][j] = temp;
            }
        }
        //对角线翻转：遍历对角线左半边，和对角线右半交换位置，只需要遍历对角线一端
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        int[][] matrix2 = new int[][] {
                {5,1,9,11},
                {2,4,8,10},
                {13,3,6,7},
                {15,14,12,16}
        };
        new Test20().rotate(matrix2);
    }
}
